1. Field of the Invention
The present invention relates to a zero knowledge interactive protocol wherein the prover convinces the verifier of a statement without revealing it, using the mismatch between discrete logarithms employed in undeniable signatures which the prover cannot deny their validity if they were produced by the prover himself.
2. Description of the Related Art
Undeniable signatures are electronic signatures proposed by D. Chaum. This cryptographic technique employs a number system having a group G of order q of mod p (where p and q are prime numbers and the relation q|(p−1) holds, i.e., (p−1) is divisible by q. The signer uses y=gx (i.e., an element of the group G) and the primitive element g as a public key and uses x as a private key. A signature SIG on a message m is performed by the signer computing SIG=mx. If it can be shown that, for a signature (m, SIG), the discrete log x′ to the base m of SIG=mx′ equals the discrete log x to the base g of a relation y=gx, the signature is said to be verified. If SIG′≠mx is shown for a signature (m, SIG′), it can be said that the signature is a fake. In general terms, the undeniable signature system requires that the prover must show equality/inequality between the discrete log of an input value y to the base g and the discrete log of an input value SIG to the base m and that the verifier must confirm this relation.
A prior art undeniable signature protocol is disclosed in the literature by D. Chaum “Zero-Knowledge Undeniable Signatures, Advance in Cryptology, Proceedings of Eurocrypt '90, LNCS 473, Springer-Verlag, pp. 458-464, 1991. As shown in FIG. 1, a typical example of a cryptographic communication system based on the zero-knowledge undesirable signature protocol is comprised of a prover 500 and a verifier 550, interconnected by a communications channel. Prover 500 is connected to a private key memory 501, a public key memory 502 and a random number generator 503. The element x of Z/qZ is stored in the private key memory 501. Prime numbers p and q of sufficiently large value having the relation q|(p−1), and elements g, m, z of a subgroup Gq of order q of (Z/pZ)* are stored in the public key memory 502 (note that z≠mx mod p). Verifier 550 is associated with a public key memory 551 and a random number generator 552. In the public key memory 551 the verifier 550 shares the same public key information as that of the prover 500. Prover 500 establishes a proof that z≠mx without revealing x to the verifier 550. Verifier 550 uses the random number generator 552 to generate a random value “x” smaller than “k” and a random value “a” as an element of Z/qZ, and computes c[1]=msga mod p and c[2]=zs(gx)a mod p (block 553) and transmits a message 561 containing the results of the computations c[1] and c[2] to the prover 500. In response, the prover 500 makes a search through values 1 to k for detecting a value s′ that satisfies the relation c[1]x/c[2]=(mx/z)s′ mod p (block 504). As long as the verifier 550 behaves legitimately and the relation z≠mx holds, this search results in the finding of a unique value s′ which corresponds to a value the verifier 550 would find. Since the value s′ found by the prover 500 satisfies the relation z=mx mod p, the probability that the verifier 550 selects the value s′ is 1/k. Prover 500 uses the random number generator 503 to generate a random value “r” and uses it to generate a commitment of s′ (block 505) and transmits commit (r, s′) to the verifier 550. Verifier 550 responds to it by sending the random value “a” which was generated in the random number generator 55 (block 554). Using the transmitted random value, the prover 500 checks to see that if relations c[1]=ms′ga mod p and c[2]=zs′(gx)a mod p are established (block 506). If the prover 500 confirms that these relations hold, it replies with the random value “r”. In response to receipt of this random value, the verifier 550 determines whether s′ coincides with s (block 555). If s′=s, the verifier 550 accepts the response as a valid proof; otherwise, it denies the response, thus completing a round of interactions (block 556). This round of interactions is repeated so that the probability of prover 500 cheating the verifier 550 is sufficiently reduced.
In the Chaum's zero-knowledge signature system, the prover is required to make a search for s′ in the range of values 1 to k that satisfies the relation c[1]x/c[2]=(mx/z)s′ mod p. Since this search involves a sequence of determinations each using a different value of s′ on a trial-and-error basis, the system works at low efficiency. Furthermore, in each round of interactions, the verifier is required to generate a random value s and send it to the prover. Therefore, proof is impossible without sending messages from the verifier to the prover.
Another prior art undeniable signature is disclosed by M. Michels et al., in the literature “Efficient Convertible Undeniable Signature Schemes”, Proceedings of 4th Annual Workshop on Selected Areas in Cryptography, SAC '97, August 1997. This prior art protocol allows the prover to prove his own signature without assistance from the verifier. However, the prover is required to transmit the parameter mx to the verifier, indicating that “no signature is made on the secret message”. Since the revealing of this information to the verifier implies that a signature has been unintentionally handed over to the verifier, the circumstance resulting from the transmission of mx contradicts its intended purpose.